package com.liuzhilong.infrastructure.framework.algorithms.datastruct.tree;

import java.util.Arrays;

import static com.liuzhilong.infrastructure.framework.algorithms.datastruct.tree.TreeUtils.Arrays.*;
/**
 * 堆。<br>
 * 堆是一种特殊的二叉树，总是满二叉树的结构。特性是父节点总比子节点大或者总比子节点小。
 * @author longandai@163.com
 */
public class Heap {

    private Integer[] data;
    private int count=0;
    //是否是最小堆
    private boolean small=true;
    /**
     * shiftup操作。
     * 与父节点比对，如果不符合规则 交换
     * @param i
     */
    public void shiftUp(Integer[] array,int i ){
        if(i==0){//顶点不需要交换
            return;
        }
        if((small&&(data[i]<data[parent(i)]))||(!small&&(data[i]>data[parent(i)]))){
            swap(i, parent(i));
            //查看父节点是否需要交换
            shiftUp(array,parent(i) );
        }
    }
    /**
     * 与子元素对比 如果不符合条件 下沉
     * @param i
     */
    public void shiftDown(Integer[] array,int i){
        //查看是否越界
        if(left(i)>=count){
            return;
        }
        if(right(i)>=count){
            //右侧越界
            //只判断左侧

            //两个节点都是空的 不继续
            if(data[left(i)]==null){
                return;
            }
            if(small&&(data[left(i)]<data[i])){
                //获取比较小的
                swap(i,left(i));
            }
            if(!small&&(data[left(i)]>data[i])){
                //获取比较小的
                swap(i,left(i));
            }


            return;
        }

        //两个节点都是空的 不继续
        if(data[left(i)]==null&&data[right(i)]==null){
            return;
        }
        if(small&&(data[left(i)]<data[i]||data[right(i)]<data[i])){
            //获取比较小的
            int index = data[right(i)]==null||data[left(i)]<data[right(i)]?left(i):right(i);
            swap(i,index);
            shiftDown(array,index);
        }
        if(!small&&(data[left(i)]>data[i]||data[right(i)]>data[i])){
            //获取比较小的
            int index = data[right(i)]==null||data[left(i)]>data[right(i)]?left(i):right(i);
            swap(i,index);
            shiftDown(array,index);
        }
    }
    public void insert(int item){
        if(count == data.length){
            //扩容 TODO
            throw new RuntimeException("容量不足");
        }
        //插入最后元素
        data[count]=item;
        shiftUp(data,count++);
    }
    //获取栈顶元素
    public Integer pop(){
        if(count<=0){
            return null;
        }
        Integer top = data[0];
        data[0] = null;
        swap(0,--count);
        shiftDown(data,0);
        return top;
    }

//    public Heap(int[] data,boolean small) {
//        this.data = data;
//        this.small = small;
//    }
    public Heap(int size,boolean small) {
        //强制扩展为两倍size
        this.data = new Integer[size];
        this.small = small;
        this.count = 0;
    }

    /**
     * 使用heapify方法，从最后一个非叶子节点开始，从下往上，对每个节点执行下沉(siftDown)操作，这样一开始就排除了一半的节点
     */
    private void heapify(){
        for(int i=parent(count-1);i>=0;i--){
            shiftDown(data,i);
        }
    }
    /**
     * 给定一个数据，有两种方式把这个数组变成堆。<br>

     * 第一个：从第二个元素开始，循环遍历，执行shiftUp<br>
     * 第二种：使用heapify方法，从最后一个非叶子节点开始，从下往上，对每个节点执行下沉(siftDown)操作，这样一开始就排除了一半的节点
     * @param data
     * @param small
     */
    public Heap(Integer[] data,boolean small) {
        this.data = data;
        this.small = small;
        this.count = data.length;
        heapify();
    }
    public Integer[] getData() {
        return data;
    }

    public int getCount() {
        return count;
    }

    public void setCount(int count) {
        this.count = count;
    }

    private void swap(int i, int j) {
        Integer id = data[i];
        data[i] = data[j];
        data[j] = id;
    }

    /**
     * 堆排序的实现方法
     */
    public Integer[] sort(){
        while (count>0){
            swap(0,--count);
            shiftDown(data,0);
        }
        return data;

    }
    public static void main(String[] args) {
        Heap heap = new Heap(new Integer[]{99,28,10,23,128,12,4,56,1,23,444}, false);
//        for (int i = 0; i < 16; i++) {
//            heap.insert(i);
//        }
        System.out.println(heap.getData());

        while (heap.getCount()>0){
            System.out.println(heap.pop());
        }
    }




}
